package violentRecursion;

/**
 * @className: LeetCode_97
 * @Description: 交错字符串
 * @author: kunkun
 * @date: 2025/7/10 17:31
 */
class LeetCode_97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length()+s2.length()!=s3.length()){
            return false;
        }
        return solution_2(0,0,s1,s2,s3);
    }

    /**
     * @Author kunkun
     * @Description 动态规划
     * @Date 17:38 2025/7/10
     **/
    private boolean solution_2(int x,int y, String s1, String s2, String s3) {
        boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
        dp[s1.length()][s2.length()]=true;
        for (int i = s1.length(); i >=0; i--) {
            for (int j = s2.length(); j >=0 ; j--) {
                if (i == s1.length() && j==s2.length()){
                    continue;
                }
                Boolean res1=false,res2=false;
                if (i<s1.length() && s1.charAt(i)==s3.charAt(i+j)){
                    res1=dp[i+1][j];
                }
                if (j<s2.length() && s2.charAt(j)==s3.charAt(i+j)){
                    res2=dp[i][j+1];
                }
                dp[i][j]= res1||res2;
            }
        }
        return dp[0][0];
    }

    /**
     * @Author kunkun
     * @Description 暴力递归
     * @Date 17:38 2025/7/10
     **/
    private boolean solution_1(int i, int j, String s1, String s2, String s3) {
        if (i==s1.length() && j==s2.length() && i+j==s3.length()){
            return true;
        }
        Boolean res1=false,res2=false;
        if (i<s1.length() && s1.charAt(i)==s3.charAt(i+j)){
            res1=solution_1(i+1,j,s1,s2,s3);
        }
        if (j<s2.length() && s2.charAt(j)==s3.charAt(i+j)){
            res2=solution_1(i,j+1,s1,s2,s3);
        }
        return res1||res2;
    }
}
